package random;

import java.util.AbstractMap;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

public class YAASawGridLong  implements ASawGrid {

	private final int size;
	
	private final ArrayMap mapHL;

	private final ArrayMap mapVL;

	private final ArrayMap mapHS;

	private final ArrayMap mapVS;

	private final int cellSize;

	private final int threshold;

	public YAASawGridLong(int cellSize, int size, int threshold) {
		super();
		this.cellSize = cellSize;
		this.size = size;
		this.threshold = threshold;
		this.mapHL = new ArrayMap(size);
		this.mapVL = new ArrayMap(size);
		this.mapHS = new ArrayMap(size);
		this.mapVS = new ArrayMap(size);
	}

	public final boolean intersectV(final int x, final int y, final int length) {
		final int min = length > 0 ? x + 1 : x + length;
		final int max = length > 0 ? x + length : x - 1;
		{
			final int[] coord = { min / this.cellSize, y / this.cellSize };
			{
				final List<int[]> list = mapVL.get(coord);
				if (list != null) {
					final ListIterator<int[]> it = list.listIterator(list.size());
					while (it.hasPrevious()) {
						int[] i = it.previous();
						if (min <= i[0] && i[0] <= max && i[1] <= y && y <= i[2]) {
							return true;
						}
					}
				}
			}{
				final List<int[]> list = mapVS.get(coord);
				if (list != null) {
					final ListIterator<int[]> it = list.listIterator(list.size());
					while (it.hasPrevious()) {
						int[] i = it.previous();
						if (min <= i[0] && i[0] <= max && i[1] <= y && y <= i[2]) {
							return true;
						}
					}
				}
			}
		}
		if (min / this.cellSize != max / this.cellSize) {
			final int[] coord = { max / this.cellSize, y / this.cellSize };
			{
				final List<int[]> list = mapVL.get(coord);
				if (list != null) {
					final ListIterator<int[]> it = list.listIterator(list.size());
					while (it.hasPrevious()) {
						int[] i = it.previous();
						if (min <= i[0] && i[0] <= max && i[1] <= y && y <= i[2]) {
							return true;
						}
					}
				}
			}{
				final List<int[]> list = mapVS.get(coord);
				if (list != null) {
					final ListIterator<int[]> it = list.listIterator(list.size());
					while (it.hasPrevious()) {
						int[] i = it.previous();
						if (min <= i[0] && i[0] <= max && i[1] <= y && y <= i[2]) {
							return true;
						}
					}
				}
			}
		}
		return false;

	}

	public final boolean intersectH(final int x, final int y, final int length) {
		final int min = length > 0 ? y + 1 : y + length;
		final int max = length > 0 ? y + length : y - 1;
		{
			final int[] coord = { x / this.cellSize, min / this.cellSize };
			{
				final List<int[]> list = mapHL.get(coord);
				if (list != null) {
					final ListIterator<int[]> it = list.listIterator(list.size());
					while (it.hasPrevious()) {
						int[] i = it.previous();
						if (min <= i[0] && i[0] <= max && i[1] <= x && x <= i[2]) {
							return true;
						}
					}
				}
			}{
				final List<int[]> list = mapHS.get(coord);
				if (list != null) {
					final ListIterator<int[]> it = list.listIterator(list.size());
					while (it.hasPrevious()) {
						int[] i = it.previous();
						if (min <= i[0] && i[0] <= max && i[1] <= x && x <= i[2]) {
							return true;
						}
					}
				}
			}
		}
		if (min / this.cellSize != max / this.cellSize) {
			final int[] coord = { x / this.cellSize, max / this.cellSize };
			{
				final List<int[]> list = mapHL.get(coord);
				if (list != null) {
					final ListIterator<int[]> it = list.listIterator(list.size());
					while (it.hasPrevious()) {
						int[] i = it.previous();
						if (min <= i[0] && i[0] <= max && i[1] <= x && x <= i[2]) {
							return true;
						}
					}
				}
			}{
				final List<int[]> list = mapHS.get(coord);
				if (list != null) {
					final ListIterator<int[]> it = list.listIterator(list.size());
					while (it.hasPrevious()) {
						int[] i = it.previous();
						if (min <= i[0] && i[0] <= max && i[1] <= x && x <= i[2]) {
							return true;
						}
					}
				}
			}
		}
		return false;

	}

	public final void addH(final int x, final int y, final int length) {
		final int min = length > 0 ? x : x + length;
		final int max = length > 0 ? x + length : x;
		if (Math.abs(length) > this.threshold) {
			{
				final int[] coord = { min / this.cellSize, y / this.cellSize };
				addHL(y, min, max, coord);
			}
			if (min / this.cellSize != max / this.cellSize) {
				final int[] coord = { max / this.cellSize, y / this.cellSize };
				addHL(y, min, max, coord);
			}
		} else {
			{
				final int[] coord = { min / this.cellSize, y / this.cellSize };
				addHS(y, min, max, coord);
			}
			if (min / this.cellSize != max / this.cellSize) {
				final int[] coord = { max / this.cellSize, y / this.cellSize };
				addHS(y, min, max, coord);
			}
		}
	}
	
//	private int maxi= 0;

	private final void addHL(final int y, final int min, final int max, final int[] coord) {
		List<int[]> list = mapHL.get(coord);
		if (list == null) {
			list = new LinkedList<int[]>();
			mapHL.put(coord, list);
		}
//		if(list.size()>maxi){
//			maxi = list.size();
//			System.out.println("L"+maxi);
//		}
		{
			final int[] i = { y, min, max };
			final int size1;
			final List<int[]> lVS;
			final int lVSsize;
			if ((size1 = list.size()) > 2 && (lVS = mapVS.get(coord)) != null && (lVSsize = lVS.size()) >= 2) {
				final ListIterator<int[]> li = list.listIterator(size1);
				final int[] i1 = li.previous();
				final int y1 = i1[0];
				if (y < y1) {
					if (y1-y==1 && i1[1] == min && i1[2] == max) {
						final int[] i2 = li.previous();
						if (i2[0] - y == 2 && i2[1] == min && i2[2] == max) {
							final int[] i3 = li.previous();
							final int y3 = i3[0];
							if (y < i3[0] && i3[1] == min && i3[2] == max) {
								final ListIterator<int[]> liVS = lVS.listIterator(lVSsize);
								final int[] v1 = liVS.previous();
								final int[] v2 = liVS.previous();
								if ((v1[0] == min && v2[0] == max) || (v1[0] == max && v2[0] == min)) {
									final int ma = Math.min(v1[2], v2[2]);
									final int mi = Math.max(v1[1], v2[1]);
									if (mi <= y1 && ma >= y3 - 1) {
										li.next();
										li.next();
										li.remove();
										li.next();
										li.add(i);
										return;
									}
								}
								if (min / this.cellSize != max / this.cellSize) {
									final int[] coordmi = {min/this.cellSize,y/this.cellSize}; 
									final List<int[]> lVSmi = mapVS.get(coordmi);
									final int[] coordma = {max/this.cellSize,y/this.cellSize}; 
									final List<int[]> lVSma = mapVS.get(coordma);
									if(lVSmi != null && lVSma != null){
										final int[] vmi = lVSmi.get(lVSmi.size()-1);
										final int[] vma = lVSma.get(lVSma.size()-1);
										if (vmi[0] == min && vma[0] == max) {
											final int ma = Math.min(vmi[2], vma[2]);
											final int mi = Math.max(vmi[1], vma[1]);
											if (mi <= y1 && ma >= y3 - 1) {
												li.next();
												li.next();
												li.remove();
												li.next();
												li.add(i);
												return;
											}
										}
									}
								}
							}
						}
					}
				}else{
					if (y-y1==1 && i1[1] == min && i1[2] == max) {
						final int[] i2 = li.previous();
						if (i2[0] - y == -2 && i2[1] == min && i2[2] == max) {
							final int[] i3 = li.previous();
							final int y3 = i3[0];
							if (y > i3[0] && i3[1] == min && i3[2] == max) {
								final ListIterator<int[]> liVS = lVS.listIterator(lVSsize);
								final int[] v1 = liVS.previous();
								final int[] v2 = liVS.previous();
								if ((v1[0] == min && v2[0] == max) || (v1[0] == max && v2[0] == min)) {
									final int ma = Math.min(v1[2], v2[2]);
									final int mi = Math.max(v1[1], v2[1]);
									if (mi <= y3 && ma >= y1 - 1) {
										li.next();
										li.next();
										li.remove();
										li.next();
										li.add(i);
										return;
									}
								}
								if (min / this.cellSize != max / this.cellSize) {
									final int[] coordmi = {min/this.cellSize,y/this.cellSize}; 
									final List<int[]> lVSmi = mapVS.get(coordmi);
									final int[] coordma = {max/this.cellSize,y/this.cellSize}; 
									final List<int[]> lVSma = mapVS.get(coordma);
									if(lVSmi != null && lVSma != null){
										final int[] vmi = lVSmi.get(lVSmi.size()-1);
										final int[] vma = lVSma.get(lVSma.size()-1);
										if (vmi[0] == min && vma[0] == max) {
											final int ma = Math.min(vmi[2], vma[2]);
											final int mi = Math.max(vmi[1], vma[1]);
											if (mi <= y3 && ma >= y1 - 1) {
												li.next();
												li.next();
												li.remove();
												li.next();
												li.add(i);
												return;
											}
										}
									}
								}
							}
						}
					}
				}
			}
			list.add(i);
		}
	}

	private final void addHS(final int y, final int min, final int max, final int[] coord) {
		List<int[]> list = mapHS.get(coord);
		if (list == null) {
			list = new LinkedList<int[]>();
			mapHS.put(coord, list);
		}
//		if(list.size()>maxi){
//			maxi = list.size();
//			System.out.println("S"+maxi);
//		}
		{
			int s;
			if((s = list.size()) > 2){
				final ListIterator<int[]> li = list.listIterator(s);
				int[] i1 = li.previous();
				boolean dir;
				if (i1[0]==y && ((dir=(i1[1]-max==1)) || min - i1[2] == 1) ) {
					final int[] i = { y, dir?min:i1[1], dir?i1[2]:max };
					li.set(i);
					return;
				}
				int[] i2 = li.previous();
				boolean dir2;
				if (i2[0]==y && ((dir2=(i2[1]-max==1)) || min - i2[2] == 1) ) {
					final int[] i = { y, dir2?min:i2[1], dir2?i2[2]:max };
					li.set(i);
					return;
				}
			}
			final int[] i = { y, min, max };
			list.add(i);
		}
	}

	public final void addV(final int x, final int y, final int length) {
		final int min = length > 0 ? y : y + length;
		final int max = length > 0 ? y + length : y;
		if (Math.abs(length) > this.threshold) {
			{
				final int[] coord = { x / this.cellSize, min / this.cellSize };
				addVL(x, min, max, coord);
			}
			if (min / this.cellSize != max / this.cellSize) {
				final int[] coord = { x / this.cellSize, max / this.cellSize };
				addVL(x, min, max, coord);
			}
		} else {
			{
				final int[] coord = { x / this.cellSize, min / this.cellSize };
				addVS(x, min, max, coord);
			}
			if (min / this.cellSize != max / this.cellSize) {
				final int[] coord = { x / this.cellSize, max / this.cellSize };
				addVS(x, min, max, coord);
			}
		}
	}

	private final void addVL(final int x, final int min, final int max, final int[] coord) {
		List<int[]> list = mapVL.get(coord);
		if (list == null) {
			list = new LinkedList<int[]>();
			mapVL.put(coord, list);
		}
//		if(list.size()>maxi){
//			maxi = list.size();
//			System.out.println("L"+maxi);
//		}
		{
			final int[] i = { x, min, max };
			final int size1;
			final List<int[]> lHS;
			final int lHSsize;
			if ((size1 = list.size()) > 2 && (lHS = mapHS.get(coord)) != null && (lHSsize = lHS.size()) >= 2) {
				final ListIterator<int[]> li = list.listIterator(size1);
				final int[] i1 = li.previous();
				final int x1 = i1[0];
				if (x < x1) {
					if (x1-x==1 && i1[1] == min && i1[2] == max) {
						final int[] i2 = li.previous();
						if (i2[0] - x == 2 && i2[1] == min && i2[2] == max) {
							final int[] i3 = li.previous();
							final int x3 = i3[0];
							if (x < i3[0] && i3[1] == min && i3[2] == max) {
								final ListIterator<int[]> liHS = lHS.listIterator(lHSsize);
								final int[] v1 = liHS.previous();
								final int[] v2 = liHS.previous();
								if ((v1[0] == min && v2[0] == max) || (v1[0] == max && v2[0] == min)) {
									final int ma = Math.min(v1[2], v2[2]);
									final int mi = Math.max(v1[1], v2[1]);
									if (mi <= x1 && ma >= x3 - 1) {
										li.next();
										li.next();
										li.remove();
										li.next();
										li.add(i);
										return;
									}
								}
								if (min / this.cellSize != max / this.cellSize) {
									final int[] coordmi = {x/this.cellSize,min/this.cellSize}; 
									final List<int[]> lHSmi = mapHS.get(coordmi);
									final int[] coordma = {x/this.cellSize,max/this.cellSize}; 
									final List<int[]> lHSma = mapHS.get(coordma);
									if(lHSmi != null && lHSma != null){
										final int[] vmi = lHSmi.get(lHSmi.size()-1);
										final int[] vma = lHSma.get(lHSma.size()-1);
										if (vmi[0] == min && vma[0] == max) {
											final int ma = Math.min(vmi[2], vma[2]);
											final int mi = Math.max(vmi[1], vma[1]);
											if (mi <= x1 && ma >= x3 - 1) {
												li.next();
												li.next();
												li.remove();
												li.next();
												li.add(i);
												return;
											}
										}
									}
								}
							}
						}
					}
				}else{
					if (x-x1==1 && i1[1] == min && i1[2] == max) {
						final int[] i2 = li.previous();
						if (i2[0] - x == -2 && i2[1] == min && i2[2] == max) {
							final int[] i3 = li.previous();
							final int x3 = i3[0];
							if (x > i3[0] && i3[1] == min && i3[2] == max) {
								final ListIterator<int[]> liHS = lHS.listIterator(lHSsize);
								final int[] v1 = liHS.previous();
								final int[] v2 = liHS.previous();
								if ((v1[0] == min && v2[0] == max) || (v1[0] == max && v2[0] == min)) {
									final int ma = Math.min(v1[2], v2[2]);
									final int mi = Math.max(v1[1], v2[1]);
									if (mi <= x3 && ma >= x1 - 1) {
										li.next();
										li.next();
										li.remove();
										li.next();
										li.add(i);
										return;
									}
								}
								if (min / this.cellSize != max / this.cellSize) {
									final int[] coordmi = {x/this.cellSize,min/this.cellSize}; 
									final List<int[]> lHSmi = mapHS.get(coordmi);
									final int[] coordma = {x/this.cellSize,max/this.cellSize}; 
									final List<int[]> lHSma = mapHS.get(coordma);
									if(lHSmi != null && lHSma != null){
										final int[] vmi = lHSmi.get(lHSmi.size()-1);
										final int[] vma = lHSma.get(lHSma.size()-1);
										if (vmi[0] == min && vma[0] == max) {
											final int ma = Math.min(vmi[2], vma[2]);
											final int mi = Math.max(vmi[1], vma[1]);
											if (mi <= x3 && ma >= x1 - 1) {
												li.next();
												li.next();
												li.remove();
												li.next();
												li.add(i);
												return;
											}
										}
									}
								}
							}
						}
					}
				}
			}
			list.add(i);
		}
	}

	private final void addVS(final int x, final int min, final int max, final int[] coord) {
		List<int[]> list = mapVS.get(coord);
		if (list == null) {
			list = new LinkedList<int[]>();
			mapVS.put(coord, list);
		}
//		if(list.size()>maxi){
//			maxi = list.size();
//			System.out.println("S"+maxi);
//		}
		{
			int s;
			if((s = list.size()) > 2){
				final ListIterator<int[]> li = list.listIterator(s);
				final int[] i1 = li.previous();
				boolean dir;
				if (i1[0]==x && ((dir=(i1[1]-max==1))|| min - i1[2] == 1) ) {
					final int[] i = { x, dir?min:i1[1], dir?i1[2]:max };
					li.set(i);
					return;
				}
				final int[] i2 = li.previous();
				boolean dir2;
				if (i2[0]==x && ((dir2=(i2[1]-max==1)) || min - i2[2] == 1) ) {
					final int[] i = { x, dir2?min:i2[1], dir2?i2[2]:max };
					li.set(i);
					return;
				}
			}
			final int[] i = { x, min, max };
			list.add(i);
		}
	}

//	public final class ArrayMap {
//		
//		private final int size;
//		
//		public ArrayMap(int size){
//			this.size = size;
//		}
//
//		private final List<int[]>[][] arr = new List[this.size][];
//
//		private final void put(int[] key, List<int[]> value) {
//			final int x = key[0];
//			final int y = key[1];
//			List<int[]>[] a;
//			if ((a = arr[x]) == null) {
//				a = arr[x] = new List[this.size];
//			}
//			a[y] = value;
//			return;
//		}
//
//		private final List<int[]> get(int[] key) {
//			final int x = key[0];
//			final int y = key[1];
//			final List<int[]>[] a;
//			if ((a = arr[x]) == null) {
//				return null;
//			}
//			return a[y];
//		}
//
//	}
}
